package link;

import java.util.ArrayList;
import java.util.List;

/**
 * 峰值元素是指其值严格大于左右相邻值的元素。
 *
 * 给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
 *
 * 你可以假设 nums[-1] = nums[n] = -∞ 。
 *
 * 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
 *
 */
public class leetCode162_findPeakElement {

    public int findPeakElement(int[] nums) {
        if(nums == null || nums.length == 0) return -1;
        if(nums.length == 1) return 0;
        if(nums[0] > nums[1]){
            return 0;
        }
        int n = nums.length;
        if(nums[n - 2] < nums[n - 1]) return n - 1;
        List<Integer> tmp1 = new ArrayList<>();
        for (int i = 1; i < nums.length; i++) {
            if(nums[i] > nums[i - 1]){
                tmp1.add(i);
            }
        }

        for (int i = nums.length - 1; i > 0; i--) {
            if(nums[i] > nums[i - 1]){
                if(tmp1.contains(i)){
                    return i;
                }
            }
        }
        return -1;
    }

    public int findPeakElement2c(int[] nums) {
        if(nums == null || nums.length == 0) return -1;
        if(nums.length == 1) return 0;
        if(nums[0] > nums[1]){
            return 0;
        }
        int n = nums.length;
        if(nums[n - 2] < nums[n - 1]) return n - 1;
        int l = 1;
        int r = n - 2;
        // 因为边界是负无穷，所以往递增的方向找，一定能找到峰值
        while (l < r){
            int mid = l + (r - l)/2;
            //说明右边已经有边界了，说明从mid到负无穷肯定有峰值
            if(nums[mid] > nums[mid + 1]){
                r = mid;
            }else if(nums[mid] <= nums[mid + 1]){
                // 左边小，还没找到峰值，继续找
                l = mid + 1;
            }
        }
        return r;
    }


}
